#include <vector>
#include<array>
#include<string>
class Solution {
public:
    const static int MAX = 10001;
    std::array<std::array<int,26>,MAX> tree;
    std::array<int,MAX> path;
    std::array<std::string, MAX> end;
    int cnt = 1;
    std::vector<std::string> findWords(std::vector<std::vector<char>>& board,
        std::vector<std::string>& words) {
        build(words);
        std::vector<std::string> res;
        for (int i=0;i<board.size();i++)
        {
            for (int j=0;j<board[0].size();j++)
            {
                dfs(board,i,j,1,res);
            }
        }
        return res;
    }
    int dfs(std::vector<std::vector<char>>& board, int i, int j,int t,std::vector<std::string>& ans)
    {
        if (i<0||i==board.size()||j<0||j==board[0].size()||board[i][j]==0)
            return 0;
        char tmp = board[i][j];
        int road = tmp - 'a';
        t = tree[t][road];
        if (t==0||path[t]==0)
        {
            return 0;
        }
        int fix = 0;
        if (!end[t].empty() )
        {
            fix++;
            ans.push_back(end[t]);
            end[t] = "";
        }
        board[i][j] = 0;
        fix += dfs(board,i-1,j,t,ans);
        fix+=dfs(board,i+1,j,t,ans);
        fix+=dfs(board,i,j-1,t,ans);
        fix+=dfs(board,i,j+1,t,ans);
        path[t] -= fix;
        board[i][j] = tmp;
        return fix;
    }
    void build(const std::vector<std::string> & words)
    {
        for (const auto& word : words)
        {
            insert(word);
        }
    }
    void insert(const std::string & s)
    {
        int index = 1;
        path[1]++;
        for (const auto & c : s)
        {
            int now = c - 'a';
            if (tree[index][now] ==0)
            {
                tree[index][now] = ++cnt;
            }
            index = tree[index][now];
            path[index]++;
        }
        end[index] = s;
    }
};